// PUPRTE.BPL -- MODULE IMPLEMENTING THE PUP ROUTING TABLE
// Copyright Xerox Corporation 1979

GET "PUPLIB.HDR"
GET "LEVEL0.HDR"
GET "LEVEL1.HDR"

MANIFEST
[
LENRT = 129
]

MANIFEST
[
RTTIMEOUTINTERVAL = 900		//AGE RTE'S AFTER 1.5 MINUTES
				//PURGE THEM AFTER 3 MINUTES
RTSIZE = 32
PROBEMASK = RTSIZE-1

// ROUTING INFO PROTOCOL DEFINITIONS
PSROUTEINFO = 2
PTROUTEREQUEST = #200
PTROUTEREPLY = #201
]

// THIS MODULE PLUGS INTO GATEFORWARD.BCPL - THE GATEWAY FORWARDER,
//  OR INTO PUPDUMMYGATE, IF THIS ISN'T A GATEWAY.

//----------------------------------------------------------------------------
LET INITROUTINGTABLE(ZONE) BE
//----------------------------------------------------------------------------
[
PUPRT := ALLOCATE(ZONE, LENRT)
SETBLOCK(LV PUPRT!1, RTFREEENTRY, RTSIZE*LENRTE)
PUPRT!0 := LOGRTSIZE
]

//----------------------------------------------------------------------------
AND HLOOKUP(RT, KEY, FINDFREE) = VALOF
//----------------------------------------------------------------------------
//RETURNS POINTER TO RTE MATCHING KEY, OR ZERO IF NOT FOUND.
//IF FINDFREE IS TRUE, THEN UPON FAILURE RETURNS POINTER TO
//FIRST FREE ENTRY (ZERO IF NONE).
[
LET IPROBE = NIL
LET INCREMENT = HHASH(LOGRTSIZE, KEY, LV IPROBE)
LET PROBE = IPROBE
   [
   LET RTE = LV RT!(LENRTE*PROBE+1)
   IF KEY EQ RTE!NET THEN RESULTIS RTE  //MATCH
   IF RTE!NET EQ RTFREEENTRY THEN
      TEST FINDFREE
         THEN RESULTIS RTE  //FREE ENTRY
         OR RESULTIS 0
   PROBE := (PROBE+INCREMENT) & PROBEMASK
   ] REPEATUNTIL PROBE EQ IPROBE
RESULTIS 0  //FAIL.  SEARCHED THE WHOLE TABLE
]


//----------------------------------------------------------------------------
AND HENUMERATE(RT, PROC, ARG) BE
//----------------------------------------------------------------------------
[
//CALLS PROC(RTE, ARG) FOR EVERY VALID ENTRY IN RT
FOR I = 0 TO RTSIZE-1 DO
   [
   IF RT!(4*I+1+NET) GE 0 THEN PROC(LV RT!(4*I+1), ARG)
   ]
]


//----------------------------------------------------------------------------
AND HINSERT(RT, KEY) = VALOF
//----------------------------------------------------------------------------
//RETURNS POINTER TO AN RTE WHERE KEY CAN BE INSERTED.
//KEY IS IN THE NET FIELD AND THE REST OF THE RTE IS ZEROED.
[
LET RTE = HLOOKUP(RT, KEY, TRUE)
IF RTE EQ 0 THEN SYSERR(PUPRT, ECPUPRTFULL)  //NO FREE ENTRIES
ZERO(RTE, LENRTE)
RTE!NET := KEY
RESULTIS RTE
]

//----------------------------------------------------------------------------
AND HDELETE(RT, KEY) BE
//----------------------------------------------------------------------------
[
LET RTE = HLOOKUP(RT, KEY, FALSE)
IF RTE NE 0 THEN
   [  //MARK ENTRY FREE, THEN REPEATEDLY ENUMERATE THE RT,
      //REHASHING INACCESSIBLE ENTRIES UNTIL ALL ENTRIES ARE
      //ACCESSIBLE.
   LET DONE = NIL
   RTE!NET := RTFREEENTRY
      [
      DONE := TRUE
      FOR I = 0 TO RTSIZE-1 DO
         [
         RTE := LV RT!(4*I+1)
         IF RTE!NET NE RTFREEENTRY THEN
            [
            LET NEWRTE = HLOOKUP(RT, RTE!NET, TRUE)
            IF NEWRTE!NET EQ RTFREEENTRY THEN
               [
               MOVEBLOCK(NEWRTE, RTE, LENRTE)
               RTE!NET := RTFREEENTRY
               DONE := FALSE
               BREAK
               ]

            ]
         ]
      ] REPEATUNTIL DONE
   ]   
]

//----------------------------------------------------------------------------
AND GATEWAYLISTENER() BE
//----------------------------------------------------------------------------
// THIS PROCESS LISTENS FOR GRATUITOUS ROUTING TABLE BROADCASTS FROM
//  GATEWAYS AND UPDATES OUR LOCAL ROUTING TABLE.
// IF WE ARE A GATEWAY, ALSO LISTENS FOR GATEWAY INFO REQUESTS
//  AND RESPONDS APPROPRIATELY.
// PURGES ROUTING TABLE ENTRIES THAT HAVEN'T BEEN UPDATED RECENTLY.
// GENERATES GATEWAY ROUTING INFO PROBES IF UNKNOWNNET IS NONZERO.
[
LET RECENTPROBEFLAG = NIL
LET UPDATETIMER = NIL; SETTIMER(LV UPDATETIMER, 0)
   [
   IF TIMERHASEXPIRED(LV UPDATETIMER) THEN
      [
      //EVERY 10 SECONDS AGE THE RT ENTRIES
      HENUMERATE(PUPRT, AGERTE, PUPRT)
      RECENTPROBEFLAG := FALSE
      SETTIMER(LV UPDATETIMER, 100)
      ]

   WHILE GATEWAYLISTENERSOC!IQHEAD NE 0 DO
      [
      LET PBI = DEQUEUE(LV GATEWAYLISTENERSOC!IQ)
      TEST (PBI!TYPE & #377) EQ PTROUTEREPLY
         THEN
            [
            TEST (PBI!SHOST & #377) NE (PBI!NDB)!LHOST
            THEN
               [
               PROCESSROUTEINFOREPLY(PBI)  //IGNORE OUR OWN BCSTS
               ]
            OR
               [
               RELEASEPBI(PBI)
               ]
            ]
         OR
            [
            FORWARDER(PBI)  // MAYBE THE GATEWAY KNOWS HOW TO HANDLE IT
            ] 
      ]

   IF UNKNOWNNET NE 0 & NOT RECENTPROBEFLAG THEN
      [
      //BROADCAST A ROUTING INFO REQUEST ON EACH
      //DIRECTLY-CONNECTED NETWORK
      LET PBI = GETPBI(GATEWAYLISTENERSOC, TRUE)
      IF PBI NE 0 THEN
         [
         PBI!STATUS := PBI!STATUS | #40000
         COMPLETEPUP(PBI, PTROUTEREQUEST, PUPOVBYTES)
         UNKNOWNNET := 0
         RECENTPROBEFLAG := TRUE
         ]
      ]

   FORWARDERCTX()  // LET THE GATEWAY FORWARD SOME PACKETS
   ] REPEAT
]

//----------------------------------------------------------------------------
AND AGERTE(RTE, RT) BE
//----------------------------------------------------------------------------
IF (RTE!HOPS & #77400) NE 0 & TIMERHASEXPIRED(LV RTE!RTETIMER) THEN
   TEST (RTE!RECENT & #100000)
      THEN  //FIRST TIMEOUT, MAKE ENTRY ELIGIBLE FOR REPLACEMENT
         [
         RTE!RECENT := RTE!RECENT & #77777
         SETTIMER(LV RTE!RTETIMER, RTTIMEOUTINTERVAL)
         ]
      OR HDELETE(RT, RTE!NET)  //SECOND TIMEOUT, PURGE ENTRY

//----------------------------------------------------------------------------
AND PROCESSROUTEINFOREPLY(PBI) BE
//----------------------------------------------------------------------------
// UPDATE LOCAL RT WITH STUFF IN IMAGATEWAY PUP.
// NOTE THAT THE IDENTITY OF THE DIRECTLY CONNECTED NET HAS ALREADY BEEN
// ESTABLISHED IN PUPLEVEL1, IF IT WASN'T PREVIOUSLY KNOWN.  HERE WE UPDATE
// OUR RT AS APPROPRIATE WITH EACH OF THE 4-BYTE INFO BLOCKS IN THE PUP.
[
LET NET = PBI!DNET RSHIFT 8	//DIRECTLY CONNECTED NET
LET GHOST = (PBI!SHOST & #377)	//GATEWAY HOST ON NET
IF NET NE 0 & PBI!(SSOCKET+0) EQ 0 &	// JUST BEING SUSPICIOUS...
 PBI!(SSOCKET+1) EQ PSROUTEINFO THEN
   FOR C = 1 TO PBI!LENGTH-PUPOVBYTES BY 4 DO
      [
      // COMPUTE OUR HOP COUNT TO TARGET NET VIA THIS GATEWAY.
      LET GHOPS = MIN((PBI!(WORDS+(C+1)/2) & #377), MAXHOPS)+1
      LET RTE = NIL

      // LOOK UP TARGET NET IN RT.
      NET := PBI!(WORDS+(C-1)/2) RSHIFT 8
      RTE := HLOOKUP(PUPRT, NET, FALSE)
      TEST RTE EQ 0
         THEN
            [
            // TARGET NET NOT IN RT.
            // IF TARGET NET IS INACCESSIBLE, DON'T INSERT NEW RTE FOR IT.
            IF GHOPS GR MAXHOPS LOOP
            RTE := HINSERT(PUPRT, NET)  // SETS ENTIRE RTE TO ZERO
            ]
         OR

            // TARGET NET ALREADY IN RT.  IF DIRECTLY CONNECTED, DO NOTHING.
            IF (RTE!HOPS & #77400) EQ 0 LOOP

      // UPDATE RT ENTRY WITH THIS INFO BLOCK IF
      // (1) AN RTE DIDN'T PREVIOUSLY EXIST FOR THIS NET, OR
      // (2) THE EXISTING ENTRY HAS TIMED OUT (RECENT = FALSE), OR
      // (3) THE NEW GATEWAY NET/HOST IS THE SAME AS IN THE RTE, OR
      // (4) THE NEW ROUTE HAS FEWER HOPS THAN THE EXISTING ONE.
      // NOTE THAT IF (1) WAS TRUE, A NEW RTE WILL HAVE BEEN CREATED (ABOVE),
      // WITH CONTENTS ZEROED OUT, WHICH WILL SATISFY (2) HERE.
      IF (RTE!RECENT & #100000) EQ FALSE |  // (2)
       ((PBI!NDB EQ RTE!DNDB) & (GHOST EQ (RTE!HOST & #377))) |  // (3)
       GHOPS LS ((RTE!HOPS & #77400) RSHIFT 8) THEN  // (4)
         [
         // NOTE WHETHER ANYTHING HAS REALLY CHANGED.
         UNLESS GHOPS EQ ((RTE!HOPS & #77400) RSHIFT 8) DO PUPRTCHANGED := TRUE

         // INSERT ROUTE INTO RTE.
         RTE!HOST := (RTE!HOST & #100000) + (GHOPS LSHIFT 8) + GHOST
         RTE!DNDB := PBI!NDB  //RT->NDB

         // RESET RTE TIMEOUT ONLY IF THE TARGET NET IS NOW ACCESSIBLE.
         // THE IDEA IS TO CAUSE PERMANENTLY INACCESSIBLE NETS EVENTUALLY
         // TO BE PURGED.  ACTUALLY, IN NON-GATEWAY HOSTS, WE COULD PURGE
         // INACCESSIBLE NETS IMMEDIATELY;  HOWEVER, KNOWLEDGE OF A NETWORK'S
         // INACCESSIBILITY MUST BE REMEMBERED FOR A WHILE BY GATEWAY HOSTS
         // AND PASSED AMONG THEM EXPLICITLY SO THAT ALTERNATE ROUTES WILL
         // BE DISCOVERED QUICKLY.
         IF GHOPS LE MAXHOPS THEN
            [
            RTE!RECENT := RTE!RECENT | #100000  //RECENTLY UPDATED
            SETTIMER(LV RTE!RTETIMER, RTTIMEOUTINTERVAL)
            ]
         ]
      ]
RELEASEPBI(PBI)
]